package leetcode.top100;

import leetcode.a_总结分布.Code09_单调栈问题;

import java.util.Stack;

/**
 * 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。
 * 每个柱子彼此相邻，且宽度为 1 。
 * 求在该柱状图中，能够勾勒出来的矩形的最大面积。
 * 图形见笔记。
 * 如给定的高度为 [2,1,5,6,2,3]。
 * 最大矩形为 5和6勾勒出的 10.
 * <p>
 * 见{@link Code11_GetMaxWater_装水最多的容器}
 * 见{@link Code42_MaxWater_接雨水}
 * 见{@link Code84_MaxRectangleArea1}
 * <p>
 * 单调栈相关问题{@link Code09_单调栈问题}
 *
 * @date 2020/4/6 21:48
 */
public class Code84_MaxRectangleArea1 {
    public static void main(String[] args) {
        int[] arr = {2, 1, 5, 6, 2, 3};
        System.out.println(new Code84_MaxRectangleArea1().largestRectangleArea2(arr));
    }

    /**
     * 方式1：遍历所有子数组。然后找子数组最小值，计算。
     * 优化找子数组最小值。当i固定，j从i到len遍历时，替换min。
     * 时间O(n²)
     */
    public int largestRectangleArea1(int[] heights) {
        if (heights == null || heights.length == 0) return 0;
        int res = 0;
        for (int i = 0; i < heights.length; i++) {
            int min = heights[i];
            for (int j = i; j < heights.length; j++) {
                min = Math.min(min, heights[j]);
                res = Math.max(res, min * (j - i + 1));
            }
        }
        return res;
    }

    /**
     * 方式2：遍历i，求以i为最矮的矩形的面积。最后结果肯定在这里产生。
     * 需要注意的是，对于i，要找到左右分别比i小的第一个位置。
     * 可以每次都遍历，也可以用额外空间。
     * 用额外空间，空间最差是O(N²)。
     */
    public int largestRectangleArea2(int[] heights) {
        if (heights == null || heights.length == 0) return 0;
        int[] left = new int[heights.length];
        int[] right = new int[heights.length];
        left[0] = -1;
        right[heights.length - 1] = heights.length;
        //最差是O(N²),事实上，趋近于O(N)级别
        for (int i = 1; i < heights.length; i++) {
            int temp = i - 1;
            while (temp >= 0 && heights[i] <= heights[temp]) {
//                temp--;
                //由于heights[temp] >= heights[i],
                // left[temp] < heights[temp],并且是离temp最近的一个
                // 其中left[temp] +1 - heights[temp]都比heights[temp]大
                // 也就都比heights[i]大，所以这样写可以加速
                temp = left[temp];
            }
            left[i] = temp;
        }
        for (int i = heights.length - 2; i >= 0; i--) {
            int temp = i + 1;
            while (temp < heights.length && heights[i] <= heights[temp]) {
                //同样道理加速
                //right[temp]到heights[temp]内所有元素都比heights[temp]大，
                // 也就都比heights[i]大
                temp = right[temp];
            }
            right[i] = temp;
        }
        //遍历更新
        int res = 0;
        for (int i = 0; i < heights.length; i++) {
            res = Math.max(res, (right[i] - left[i] - 1) * heights[i]);
        }
        return res;
    }

    /**
     * 方式3：使用单调栈。
     * 根据方式2的灵感，计算每个以i为最低高度的矩形面积。
     * 现在有一个栈，非递减。一开始放入-1，代表InterMinValue。
     * 从0开始放入stack。直到遇到i，其中a[i] > a[i+1]。
     * 也就是stack中对应的数组元素非递减。
     * 此时假设栈中元素为-1,m,m+1,....i。 其中a[i]>a[i+1]。
     * 现在从i开始出栈，一直到满足stack.pop >= a[i+1]。
     * 所有出栈位置i，我们计算以该位置为最低点的矩形面积。
     * s = i+1  - stack.peek - 1。
     * 遍历完毕后，最后再单独处理栈中剩余元素。
     * 这样就保证每个位置都会计算到。
     * <p>
     * 要注意：右侧比当前位置小的是i，左侧比当前位置小的是stack.peek。
     * 遍历完后，如果stack非空，右侧是a.len。
     */
    public int largestRectangleArea3(int[] heights) {
        if (heights == null || heights.length == 0) return 0;
        //非递减栈
        Stack<Integer> stack = new Stack<>();
        //注意-1位置，代表Inter.MIN_VALUE，必须要有
        stack.push(-1);
        int area = 0;
        for (int i = 0; i < heights.length; i++) {
            //对于位置i，从栈中弹出比arr[i]都大的元素，依次计算面积

            //比如弹出的是j，那么就计算以j为最底点的矩形的面积。从 j到 i -1位置
            while (stack.peek() != -1 && heights[stack.peek()] > heights[i]) {
                int cur = stack.pop();
                //第一个比arr[cur]小的位置,left到cur之间的数有可能比arr[cur]大。
                int left = stack.peek();
                int right = i;
                //从left+1到 i-1 形成的面积
                area = Math.max(area, heights[cur] * (right - left - 1));
            }
            stack.push(i);
        }
        //最后栈中元素非递减，从最后一个位置处理。最右侧是heigth.len，左侧是当前位置
        while (stack.peek() != -1) {
            int cur = stack.pop();
            //第一个比arr[cur]小的位置,left到cur之间的数有可能比arr[cur]大。
            int left = stack.peek();
            int right = heights.length;
            //从left+1到 i-1 形成的面积
            area = Math.max(area, heights[cur] * (right - left - 1));
        }
        return area;
    }


}
